#pragma once
#include <iostream>
#include <functional>

using namespace std;

template<class K, class V>
struct Node
{
	Node<K, V>(){ next = nullptr; }
	Node<K, V>(K key, V value)
	{
		this->key = key, this->value = value, this->next = nullptr;
	}
	K key;
	V value;
	Node<K, V> *next;
};

template<class K, class V>
class HashTable
{
private:
	Node<K, V> **arr;
	int size;
	hash<K> myHash;
	
public:

	HashTable()
	{
	}

	HashTable(int size)
	{
		this->size = size;
		arr = new Node<K, V>*[size];
		for (int i = 0; i < size; i++)
		{
			arr[i] = nullptr;
		}
	}

	~HashTable()
	{
	}

	int calc_hash(K key)
	{
		int hash_key = myHash(key);
		int place = abs(hash_key) % size;
		return place;
	}

	void add(Node<K, V> *n)
	{
		Node<K, V> *temp;
		int place = calc_hash(n->key);
		if (arr[place] == nullptr)
		{
			temp = findNodeBefore(place, findNodeAfter(place));
			if (temp == nullptr)
				arr[place] = n;
			else
			{
				n->next = temp->next;
				temp->next = n;
				arr[place] = n;
			}
		}
		else
		{
			Node<K, V> *miniHead = arr[place];
			while (findNodeAfter(place) != miniHead->next)
			{
				miniHead = miniHead->next;
			}
			n->next = miniHead->next;
			miniHead->next = n;
		}
	}

	Node<K, V> *findNodeBefore(int place, Node<K, V> *n)
	{
		do
		{
			place--;
		} while (arr[place] == nullptr && place >= 1);
		Node<K, V> *head = arr[place];
		//Emptylist
		if (n == nullptr && place == 0)
			return nullptr;
		while (head->next != n)
		{
			head = head->next;
		}

		return head;
	}

	Node<K, V> *findNodeAfter(int place)
	{
		do
		{
			place++;
		} while (arr[place] == nullptr && place < size);

		if (place == size)
			return nullptr;
		else
			return arr[place];
	}

	void Print()
	{
		//cout << list.str() << endl;
		for (int i = 0; i < size; i++)
		{
			if (arr[i] != nullptr)
			{
				cout << i << endl;
				if (i < size - 1)
				{
					Node<K, V> *miniHead = arr[i];
					while (findNodeAfter(i) != miniHead->next )
					{
						cout << " " << miniHead->key << " " << miniHead->value << endl;
						miniHead = miniHead->next;
					}
					cout << " " << miniHead->key << " " << miniHead->value << endl;
				}
			}

			//" " << (*vec[i]).value << endl;
		}
	}

	/*Node<K, V> *search(K key, V value)
	{
		Node<K, V> *miniHead = vec[key];
		if (miniHead->value == "")
			return nullptr;
		else if (miniHead->value.compare(value) == 0)
			return miniHead;
		else
		{
			while (vec[key + 1] != miniHead->next)
			{
				miniHead = miniHead->next;
				if (miniHead->value.compare(value) == 0)
					return miniHead;
			}
		}
		return nullptr;
	}*/
};

